#include <iostream>

using namespace std;

// 148. 排序链表
// https://leetcode.cn/problems/sort-list/description/

typedef struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
} ListNode;

class Solution
{
public:
    ListNode *middleNode(ListNode *node)
    {
        if (node == nullptr || node->next == nullptr)
        {
            return node;
        }
        ListNode *slow = node;
        ListNode *fast = node;
        ListNode *prev = nullptr;
        while (fast != nullptr && fast->next != nullptr)
        {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        if (prev)
            prev->next = nullptr;
        return slow;
    }

    ListNode *mergeList(ListNode *l1, ListNode *l2)
    {
        ListNode outer(0);
        ListNode *curNode = &outer;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                curNode->next = l1;
                l1 = l1->next;
            }
            else
            {
                curNode->next = l2;
                l2 = l2->next;
            }
            curNode = curNode->next;
        }
        curNode->next = l1 ? l1 : l2;
        return outer.next;
    }

    ListNode *sortList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode *midde = middleNode(head);
        ListNode *left = sortList(head);
        ListNode *right = sortList(midde);
        return mergeList(left, right);
    }
};

int main()
{
    return 0;
}